1. Field of the Invention
The present invention relates generally to an adder and a multiplier circuit employing the same. More specifically, the invention relates to an adder which generates an intermediate sum of the multiplier circuit.
2. Description of the Related Art
Conventionally, a binary multiplier circuit multiplying n-bit binary values, formed with an integrated circuit, calculates logical multiplies (AND's) of respective bits of a multiplied value and multiplying value to generate n in number of n-bit partial AND's (intermediate sums), and then calculates a ground sum of the partial AND's to derive a product. As a process for deriving the ground sum, a series of full adders, in which adders of three inputs and two outputs are connected in parallel, are employed to reduce the number of the partial AND's into 2/3 at respective stages. Therefore, the number of the partial AND's is reduced in order of n.fwdarw.2/3n.fwdarw.4/9 n . . . through a plurality of stages. When the number of the partial AND's is reduced up to two, the ground sum is calculated by means of a normal adder having two inputs and one output. The multiplier circuit employing the process set forth above has been referred to as Wallace type multiplier circuit. Here, the adder with three inputs and two outputs is a circuit to perform operation to output two outputs C, S satisfying the equation 2C+S=X+Y+Z with respect to given three inputs X, Y and Z.
The conventional Wallace type multiplier circuit for multiplying two n-bit values comprises a partial AND's generating portion, an intermediate sum generating portion, in which a plurality stages of full adder series formed by connecting full adders in parallel are provided in a tree-like configuration, and the adder of two inputs and one output.
At first, by the partial AND's generating portion n in number of n-bit partial AND's, X.times.Y1, X.times.Y2, X.times.Y3, . . . X.times.Yn are calculated from a multiplied value X and multiplying value Y (Y1, Y2, Y3, . . . Yn).
Then, at the first stage of the full adder series, respective three partial AND's are input to respectively corresponding full adders. Each individual full adder receiving three input of the partial AND's outputs two intermediate sum. Therefore, through the first stage of the full adder series, the intermediate sums of two-third in number of the initial number of the partial AND's are output. In the similar manner, a number of the intermediate sums output from the first stage full adder series is reduced by two-third through the second stage full adder series. The number of stages of the intermediate sum calculating circuits can be expressed by x satisfying the equation (1/2).sup.x .multidot.n-2, and, in turn, expressed by (log n-log 2)/(log 1.5). Therefore, by (log n-log 2)/(log 1.5) in number of stages of full adder series, the number of the intermediate sums is reduced up to two. Finally, remaining two intermediate sums are input to the adder of two inputs and one output to derive the product.
The Wallace type multiplier circuit set forth above is also referred to as a carry-save adder tree.
In the intermediate sum generating process in the above-mentioned conventional multiplier circuit, the full adders of three inputs and two outputs are employed. It requires a large number of stages of the full adder series to reduce the number of the intermediate sums into two to take a long period in operation. The period required for reducing the number of the intermediate sums into two is the significant part of the overall period required for arithmetic operation including generation of the partial AND's, reduction of number of the partial AND's into two intermediate sums and adding the finally obtained two intermediate sums. Therefore, the process to reduce the number of the intermediate sums into two is a substantial barrier in speeding up of the multiplier circuit.